public class test4 {
    class Solution {
        public int maxProfit(int k, int[] prices) {
            int[][] dp = new int[prices.length][2*k+1];
            //奇：持有
            //偶（0除外）：不持有
            for(int i = 1;i<2*k;i+=2){
                dp[0][i] = -prices[0];
            }
            for(int i = 1;i<prices.length;i++){
                for(int j = 0;j<2*k-1;j+=2){
                    //偶
                    dp[i][j+2] = Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);
                    //奇
                    dp[i][j+1] = Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
                }
            }
            return dp[prices.length-1][2*k];
        }
    }
}
